给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-level-order-traversal
算法及思路
层序遍历的介绍:https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xej9yc/
层序遍历就是逐层遍历树结构。
广度优先搜索
是一种广泛运用在树或图这类数据结构中,遍历或搜索的算法。
层序遍历
每个节点都可能存储着左右子节点,所以在进入下一层前,需要将下一层的两个节点做记录
记录什么?左右子节点以及下一层的深度
如何记录?依靠队列这个数据结构(先进先出)
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
queue = deque()
ans = []
# 如果是空树,直接返回
if not root:
return ans
# 将根节点放入队列中
queue.append((0, root))
while queue:
d, node = queue.popleft()
if d == len(ans):
ans.append([])
ans[d].append(node.val)
# 将当前节点的左右子节点入队
if node.left:
queue.append((d+1, node.left))
if node.right:
queue.append((d+1, node.right))
return ans